class Solution {
    /*
        思路：Dfs即可
        值得注意的是Bfs的队列大小为O(min（m，n）)
    */
    int[][] nex = {{0,1},{1,0},{0,-1},{-1,0}};
    int n,m;
    char[][] grid;
    public int numIslands(char[][] grid) {
        this.grid = grid;
        n = grid.length;
        m = grid[0].length;
        int res = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if( grid[i][j]=='1' ){
                    res ++;
                    dfs(i,j);
                }
            }
        }
        return res;
    }
    public void dfs(int i,int j){
        grid[i][j] = '2';   // 2表示已经遍历的
        for(int k=0; k<4; k++){
            int x = i+nex[k][0];
            int y = j+nex[k][1];
            if(x<0 || x>=n || y<0 || y>=m) continue;
            if( grid[x][y] != '1' ) continue;
            dfs(x,y);
        }
    }
}